【week13】792. Number of Matching Subsequences 解题报告

792. Number of Matching Subsequences

题目

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example :
Input: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".

Note:

• All words in words and S will only consists of lowercase letters.
• The length of S will be in the range of [1, 50000].
• The length of words will be in the range of [1, 5000].
• The length of words[i] will be in the range of [1, 50].

解题报告

题意很简单，给定一个源字符串 S 和一组字符串 words，问 words 内有多少是 S 的子序列。

如果用暴力解的话这题很简单，但是时间代价是 $O(NM)$，$N$ 为 S的长度，$M$ 为 words 的长度。所以需要找更高效的算法。

// Bruth-Force
class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        vector<int> indices(words.size(), 0);
        int ans = 0;
        for (auto &ch: S) {
            for (int i = 0; i < words.size(); ++i) {
                if (indices[i] != -1 && ch == words[i][indices[i]])
                    ++indices[i];
                if (indices[i] == words[i].size()) {
                    ++ans;
                    indices[i] = -1;                  
                }
            }
        }
      	return ans;
    }
};

从暴力解法里可以看到，每次都会在一些不匹配的字符串上浪费时间。那可不可以每个字符只匹配那些可以匹配的字符串呢？

新的算法将每个 word 放在不同的队列里，这些队列以开头字母区分，那么假设现在 S 遍历到 c，我只需要将 queue[c] 中的每个 word 匹配并放进新的队列即可。这便可以省去寻找可以匹配的 word 的时间。

新的时间代价有点难表示，最坏的情况下为 $O(MN)$ ，即所有 word 都与 S 相同，最好时为 $O(N)$，即没有一个 word 可以匹配 S。可以通用地表示为 $O(\max{\sum len(subseq),N})$。其中 $subseq$ 为完全匹配或部分匹配的子序列。

Solution

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        vector<const char*> pointers[255];
        for (auto &w: words) {
            pointers[w[0]].push_back(w.c_str());
        }
        for (auto &c: S) {
            auto tmp = pointers[c];
            pointers[c].clear();
            for (auto w: tmp)
                pointers[w[1]].push_back(w + 1);
        }
        return pointers[0].size();
    }
};